package src.CodeTopSecondPractice;

public class _206 {
    // 虚拟头结点
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode newNode = new ListNode(0);
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = newNode.next;
            newNode.next = cur;
            cur = next;
        }
        return newNode.next;
    }

    // 直接反转法
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = head.next;
        while (cur != null) {
            cur.next = pre;
            pre = cur;
            cur = next;
            if (next != null) {
                next = next.next;
            }
        }
        return pre;
    }

    // 递归法
    public ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode tail = head.next;
        ListNode p = reverseList3(head.next);
        head.next = tail.next;
        tail.next = head;
        return p;
    }
}
